package com.yoshino.leetcode.improve40.threetyfirst;

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int minCost(int[][] costs) {
        // 思路：分别对每个颜色做动态规划
        int n = costs.length;
        for (int i = 1; i < n; i++) {
            costs[i][0] += Math.min(costs[i - 1][1], costs[i - 1][2]);
            costs[i][1] += Math.min(costs[i - 1][0], costs[i - 1][2]);
            costs[i][2] += Math.min(costs[i - 1][0], costs[i - 1][1]);
        }
        return Math.min(costs[n - 1][0], Math.min(costs[n - 1][1], costs[n - 1][2]));
    }

    public int minFlipsMonoIncr(String s) {
        // 对于该点翻转次数：
        // 若为 0：前一个点为 0 的翻转次数 + 判断该点是否为 0
        // 若为 1：前一个点 0,1都可（选最小），+ 判断该点是否为 1
        int dp0 = 0, dp1 = 0;
        for (int i = 0; i < s.length(); i++) {
            int dp0New = dp0, dp1New = Math.min(dp0, dp1);
            if (s.charAt(i) == '1') {
                dp0New++;
            } else {
                dp1New++;
            }
            dp0 = dp0New;
            dp1 = dp1New;
        }
        return Math.min(dp0, dp1);
    }

    public int lenLongestFibSubseq(int[] arr) {
        // 先固定 2 个
        int n = arr.length, res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], i);
        }
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 计算当前下标的两个数构成序列的个数
                dp[i][j] = Math.max(dp[i][j], 2);
                int cur = arr[i] + arr[j];
                if (map.containsKey(cur)) {
                    int ind = map.get(cur);
                    //计算移动后一位，他们构成的斐波那契数列个数
                    dp[j][ind] = dp[i][j] + 1;
                    res = Math.max(res, dp[j][ind]);
                }
            }
        }
        return res;
    }
}